|
|
Viditelnostní grafy
Král, Karel ; Valtr, Pavel (vedoucí práce) ; Balko, Martin (oponent)
V předložené práci se zabýváme viditelnostními grafy, se zaměřením na domněnku ,,velká přímka či velká klika." Pro danou množinu bodů P v rovině řekneme, že se dva body vidí, právě když otevřená úsečka mezi nimi neobsahuje žádný bod z P. Vrcholy viditelnostního grafu jsou body z P a dva body jsou spo- jeny hranou, právě když na sebe vidí. Kára a spol. vyslovili domněnku, že každá dost velká konečná množina bodů obsahuje buď ℓ bodů na jedné přímce nebo její viditelnostní graf má klikovost aspoň k. V práci zobecňujeme domněnku na širší třídu grafů a tím poskytujeme alternativní důkaz pro k = ℓ = 4. Dále shrneme dosavadní související poznatky. Zesílíme pozorování o výskytu Hamiltonovy kružnice ve viditelnostních grafech. Charakterizujeme asymptotické chování hra- nové barevnosti viditelnostních grafů. Ukážeme, že pro daná n, ℓ, k lze počítačově rozhodnout, zda původní domněnka platí. Zároveň provedeme počítačové exper- imenty jak pro zobecněnou, tak pro původní domněnku. 1
|
host ::
RSS.